Chapter 1 - Cryptographic Tools
Review Questions What are the essential ingredients of a symmetric cipher? page 42: A symmetric encryption scheme has five ingredients (Figure 2.) Plaintext: This is the original message or data that is fed into the algorithm as input. Encryption algorithm: The encryption algorithm performs various substitutions and transformations on the plaintext. Secret key: The secret key is also input to the encryption algorithm. The exact substitutions and transformations performed by the algorithm depend on the key. Ciphertext: This is the scrambled message produced as output. It depends on the plaintext and the secret key. For a given messagc, two different keys will produce two different ciphertexts. Decryption algorithm: This is essentially the encryption algorithm run in reverse. It takes the ciphertext and the secret key and produces the original plaint How many keys are required for two people to communicate via a symmetric cipher? That depends on whether you use a symmetric (shared key) or asymmetric (public/private key pair) algorithm. If you use a symmetric key, it means both people have the same key which has been pre-shared via some secure means. In that case, only one key is required; both parties in the communication use the same key to encrypt and decrypt all messages. If you use an asymmetric key algorithm, it takes at least 4 keys total: when sending a message each user will encrypt their message with the public key of the recipient (that accounts for two of the keys). Each recipient must then use their private key to decrypt the messages they receive (which accounts for the other two required keys). What are the two principal requirements for the secure use of symmetric encryption? page 43: There are two requirements for secure use of symmetric encryption: 1. We need a strong encryption algorithm. At a minimum, we would like the algorithm to be such that an opponent who knows the algorithm and has access to one or more ciphertexts would be unable to decipher the ciphertext or figure out the key. This requirement is usually stated in a stronger form: The opponent should be unable to decrypt ciphertext or discover the key even if he or she is in possession of a number of ciphertexts together with the plaintext that produced each ciphertext. Sender and receiver must have obtained copies of the secret key in a secure fashion and must keep the key secure. If someone can discover the key and knows the algorithm, all communication using this key is readable. 2. Sender and receiver must have obtained copies of the secret key in a secure fashion and must keep the key secure. If someone can discover the key and knows the algorithm, all communication using this key is readable. List three approaches to message authentication. What is a message authentication code? Message Authentication Code (MAC): (page 50) "summarizing" the message to some smaller block. The MAC is a function of the message M and a common secret key K. One-Way Hash Function: (page 52) like MAC, but does not involve an encryption key. Note: Encryption is not enough to authenticate (page 49): In fact, symmetric encryption alone is not a suitable tool for data authentica-tion. To give one simple example, in the ECB mode of encryption, if an attacker reorders the blocks of ciphertext, then each block will still decrypt successfully.However, the reordering may alter the meaning of the overall data sequence. § use of MAC and HASH to provide message authentication § PU Encrypt and Public Algorythms § PU to produce Digital Signatures Briefly describe the three schemes illustrated in Figure 2.4. Authentication using symmetric encryption, message authentication without message encryption, & message authentication code (MAC). What properties must a hash function have to be useful for message authentication? page 54: Hash-Function Requirements The purpose of a hash function is to produce a"fingerprint" of a file, message, or other block of data. To be useful for messageauthentication, a hash function H must have the following properties: H can be applied to a block of data of any size. H produces a fixed-length output. H(x) is relatively easy to compute for any given x, making both hardware andsoftware implementations practical. For any given code h, it is computationally infeasible to find x such thatH(x) = h. A hash function with this property is referred to as one-way orpreimage resistant For any given block x, it is computationally infeasible to find y != x withH(y) = H(x). A hash function with this property is referred to as secondpreimage resistant. This is sometimes referred to as weak collision resistant. It is computationally infeasible to find any pair (x, y) such that H(x) = H(y).A hash function with this property is referred to as collision resistant. This issometimes referred to as strong collision resistant. What are the principal ingredients of a public-key cryptosystem? page 57: :A public-key encryption scheme has six ingredients (Figure 2.7a): Plaintext: This is the readable message or data that is fed into the algorithm as input. Encryption algorithm: The encryption algorithm performs various transforma- tions on the plaintext. Public and private key: This is a pair of keys that have been selected so that if one is used for encryption, the other is used for decryption. The exact transfor- mations performed by the encryption algorithm depend on the public or pri- vate key that is provided as input Ciphertext: This is the scrambled message produced as output. It depends on the plaintext and the key. For a given message, two different keys will produce two different ciphertexts. Decryption algorithm: This algorithm accepts the ciphertext and the matching key and produces the original plaintext. List and briefly define three uses of a public-key cryptosystem Encryption/decryption: The sender encrypts a message with the recipient's public key. Digital signature: The sender "signs" a message with its private key. Signing is achieved by a cryptographic algorithm applied to the message or to a small block of data that is a function of the message. Key exchange: Two sides cooperate to exchange a session key. Several different approaches are possible, involving the private key(s) of one or both parties. What is the difference between a private key and a secret key? Private key - the matching pair of the public key. Secret key - the key in a symmetric cryptosystem. (page 57 footnote) What is a digital signature? A mechanism for authenticating a message. page 62: :Public-key encryption can be used for authentication, as suggested by Figure 2.6b. Suppose that Bob wants to send a message to Alice. Although it is not important that the message be kept secret, he wants Alice to be certain that the message is indeedfrom him. For this purpose, Bob uses a secure hash function, such as SHA-512, to gen- erate a hash value for the message and then encrypts the hash code with his privatekey, creating a digital signature. Bob sends the message with the signature attached. When Alice receives the message plus signature, she (1) calculates a hash value for the message; (2) decrypts the signature using Bob's public key; and (3) compares the calculated hash value to the decrypted hash value. If the two hash values match, Alice is assured that the message must have been signed by Bob. No one else has Bob's private key and therefore no one else could have created a ciphertext that could be decrypted with Bob's public key. In addition, it is impossible to alter the message without access to Bob's private key, so the message is authenticated both in terms of source and in terms of data integrity. It is important to emphasize that the digital signature does not provide confi-dentiality. That is, the message being sent is safe from alteration but not safe from eavesdropping. This is obvious in the case of a signature based on a portion of the message, because the rest of the message is transmitted in the clear. Even in the caseof complete encryption, there is no protection of confidentiality because any observer can decrypt the message by using the sender's public key. What is a public-key certificate? The problem: an attacker can pretend to be Bob (the legitimate entity) and advertise some bogus public key (not Bob's public key). Now messages intended to Bob can be decrypted by the attacker. The solution is a public-key certificate - a certificate that assures the public key is indeed Bob's. (see page 62 for details) How can public-key encryption be used to distribute a secret key? Briefly: Bob can encrypt the symmetric key using Alice's public key and send it to her. Only she can decrypt it (using her private key) and obtain the symmetric key (this still does not provide authentication - anyone can still pretend to be Bob). Problems Suppose that someone suggests the following way to confirm that the two of you are both in possession of the same secret key. You create a random bit string the length of the key, XOR it with the key, and send the result over the channel. Your partner XORs the incoming block with the key (which should be the same as your key) and sends it back. You check, and if what you receive is your original random string, you have verified that your partner has the same secret key, yet neither of you has ever transmitted the key. Is there a flaw in this scheme? Yes. Suppose Alice is an attacker that wishes to find Bob's secret key. Alice sends a random number R to Bob (not XORed). Bob XORs what he got with his key: R XOR K2 and sends this to Alice. Alice can now XOR what she got from Bob with R, to get his key: R XOR K2 XOR R = K2. Alice now has Bob's secret key. Consider a very simple symmetric block encryption algorithm, in which 32-bits blocks of plaintext are encrypted using a 64-bit key. Encryption is defined as C=(P xor K0) +K1, where C = ciphertext; K = secret key; K0 = leftmost 64 bits of K; K1 = rightmost 64 bits of K, and +K1 is addition mod 2^64. (Note: I think K0,K1 are supposed to be the 32 left/right-most bits of K) a. Show the decryption equation. That is, show the equation for P as a function of C, K1 and K2 P = (C - K1) xor K0 b. Suppose and adversary has access to two sets of plaintexts and their corresponding ciphertexts and wishes to determine K. We have the two equations: C = (P xor K0) + K1; C` = (P` xor K0) + K1 First, derive an equation in one unknown (e.g., K0). Is it possible to proceed further to solve for K0? TODO